#pragma once

#include <iostream>
#include <assert.h>
#include <unordered_map>
#include <map>
#include <thread>
#include <mutex>
#include <unistd.h>
#include <sys/mman.h>
#include "ObjectPool.h"
#include <atomic>

//using namespace std;
using std::endl;
using std::cout;

const size_t MAX_SIZE = 64 * 1024;
const size_t NFREE_LIST = 208;
const size_t MAX_PAGES = 129;
const size_t PAGE_SHIFT = 12; // 4k为页移位

// inline void *&NextObj(void *obj);

// inline void *SystemAlloc(size_t num_page);

// inline void SystemFree(void *ptr, size_t flag = 0);
inline void *&NextObj(void *obj)
{
    return *((void **)obj);
}

inline void *SystemAlloc(size_t num_page)
{
    void *ptr = mmap(0, num_page << PAGE_SHIFT, PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    // void* ptr = malloc(num_page << PAGE_SHIFT);
    if (ptr == nullptr)
        throw std::bad_alloc();

    return ptr;
}

inline void SystemFree(void *ptr, size_t flag = 0)
{
    if(flag == 0)
        munmap(ptr, (MAX_PAGES - 1) << PAGE_SHIFT);
    else
        munmap(ptr, flag << PAGE_SHIFT);
    // free(ptr);
}

class FreeList
{
public:
    void Push(void *obj)
    {
        NextObj(obj) = list;
        list = obj;
        ++num;
    }

    void *Pop()
    {
        void *obj = list;
        list = NextObj(obj);
        --num;
        return obj;
    }

    //插入到自由链表中
    void PushRange(void *head, void *tail, size_t num_)
    {
        NextObj(tail) = list;
        list = head;
        num += num_;
    }

    //从自由链表中取走内存对象
    size_t PopRange(void *&start, void *&end, size_t num_)
    {
        size_t actualNum = 0;
        void *prev = nullptr;
        void *cur = list;
        assert(list);
        for (; actualNum < num_ && cur != nullptr; ++actualNum) {
            prev = cur;
            cur = NextObj(cur);
        }

        start = list;
        end = prev;
        list = cur;
        NextObj(end) = nullptr;

        num -= actualNum;

        return actualNum;
    }

    size_t Num() { 
        return num; 
    }
    size_t MaxNum(){
        return maxnum;
    }
    void AddMaxNum(size_t num_){
        maxnum += num_;
    }
    bool Empty() { return list == nullptr; }

    void Clear()
    {
        list = nullptr;
        num = 0;
    }

private:
    void *list = nullptr;
    size_t num = 0;
    size_t maxnum = 1;
};

class SizeClass
{
public:
    // 控制在[1%，10%]左右的内碎片浪费
    static size_t _RoundUp(size_t size, size_t alignment)
    {
        return (size + alignment - 1) & (~(alignment - 1));
    }


    //对齐大小的计算，然后把申请来的内存进行划分
    static inline size_t RoundUp(size_t size)
    {
        if (size <= 128) {
            return _RoundUp(size, 8);
        } else if (size <= 1024) {
            return _RoundUp(size, 16);
        } else if (size <= 8192) {
            return _RoundUp(size, 128);
        } else {
            return _RoundUp(size, 1024);
        }
    }


    static size_t _ListIndex(size_t size, size_t align_shift)
    {
        return ((size + (1 << align_shift) - 1) >> align_shift) - 1;
    }

    //映射自由链表的位置
    static size_t ListIndex(size_t size)
    {
        assert(size <= MAX_SIZE);

        // 每个区间有多少个链
        static int group_array[4] = {16, 56, 56, 56};
        if (size <= 128) {
            return _ListIndex(size, 3);
        } else if (size <= 1024) {
            return _ListIndex(size - 128, 4) + group_array[0];
        } else if (size <= 8192) {
            return _ListIndex(size - 1024, 7) + group_array[1] + group_array[0];
        } else if (size <= MAX_SIZE) {
            return _ListIndex(size - 8192, 10) + group_array[2] + group_array[1] + group_array[0];
        }
        assert(false);
        return -1;
    }

    /*
    8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 128 共16个    
    */
    static size_t Index2Size(size_t index)
    {
        assert(index < NFREE_LIST);
        if (index < 16) {
            return (index + 1) << 3;
        } else if (index < 72) {
            return ((index - 16 + 1) << 4) + 128; 
        } else if (index < 128) {
            return ((index - 72 + 1) << 7) + 1024;
        } else if (index < 200) {
            return ((index - 128 + 1) << 10) + 8192;
        }
        return -1;
    }

    // [2,512]个之间

    //计算一次向中心缓存申请多少个节点
    static size_t NumMoveSize(size_t size)
    {
        if (size == 0)
            return 0;

        int num = MAX_SIZE / size;
        if (num < 2)
            num = 2;

        if (num > 512)
            num = 512;

        return num;
    }

    //计算一次向系统获取几个页
    static size_t NumMovePage(size_t size)
    {
        size_t num = NumMoveSize(size);
        size_t npage = num * size;

        npage >>= PAGE_SHIFT;
        if (npage == 0)
            npage = 1;

        return npage;
    }
};

typedef unsigned long long PAGE_ID;

struct Span {
    PAGE_ID pageid;   // 页号
    PAGE_ID pagenums; // 页的数量

    FreeList freelist;  // 对象自由链表
    size_t objsize; // 自由链表对象大小
    size_t usecount;   // 内存块对象使用计数
    bool isUse;

    Span *next;
    Span *prev;
    Span() : usecount(0), next(nullptr), prev(nullptr), pageid(0), pagenums(0), isUse(false) {}
};

class SpanList
{
public:
    SpanList()
    {
        head = pool.New();
        head->next = head;
        head->prev = head;
    }

    Span *Begin() { return head->next; }

    Span *End() { return head; }

    void PushFront(Span *newspan) { Insert(Begin(), newspan); }

    void PopFront() { Erase(head->next); }

    void PushBack(Span *newspan) { Insert(head, newspan); }

    void PopBack() { Erase(head->prev); }

    void Insert(Span *pos, Span *newspan)
    {
        assert(pos);
        assert(newspan);
        Span *prev = pos->prev;
        assert(prev);
        // prev newspan pos
        prev->next = newspan;
        newspan->prev = prev;

        newspan->next = pos;
        pos->prev = newspan;
    }

    void Erase(Span *pos)
    {
        assert(pos);
        assert(pos != head);

        Span *prev = pos->prev;
        Span *next = pos->next;
        assert(prev);
        assert(next);

        prev->next = next;
        next->prev = prev;
    }

    bool Empty() { return Begin() == End(); }

    void Lock() { mtx.lock(); }

    void Unlock() { mtx.unlock(); }

private:
    Span *head;
    std::mutex mtx;
    static ObjectPool<Span> pool;
};


// 自定义的哈希函数类
class HashFunc
{
public:
    int operator()(const int key)
    { //对于int类型的key对应的hash函数，随便编的，不要在意这些细节
        return 3 * key + 1;
    }
    unsigned long long operator()(const unsigned long long key) { return key; }
};

template <typename Key, typename Value> //这是链表节点，包括key和value
class HashNode
{
public:
    Key key;
    Value value;
    HashNode *next;
    HashNode(Key k, Value v) : key(k), value(v), next(NULL) {}
    ~HashNode() {}
};

template <typename Key, typename Value, typename HashFunc>
class HashMap
{
public:
    int size;
    HashFunc hash;
    HashNode<Key, Value> **table;
    static Value valuenull;

    HashMap(int _size = 10000);
    ~HashMap();
    bool insert(Key key, Value value);
    HashNode<Key, Value>* find(const Key &key);
    Value &operator[](const Key &key);
};

template <typename Key, typename Value, typename HashFunc>
Value HashMap<Key, Value, HashFunc>::valuenull = nullptr;

template <typename Key, typename Value, typename HashFunc>
HashMap<Key, Value, HashFunc>::HashMap(int _size) : size(_size), hash()
{
    table = new HashNode<Key, Value> *[size];
    for (int i = 0; i < size; i++) {
        table[i] = NULL;
    }
}

template <typename Key, typename Value, typename HashFunc>
HashMap<Key, Value, HashFunc>::~HashMap()
{
    for (int i = 0; i < size; i++) {
        HashNode<Key, Value> *cur = table[i];
        while (cur) {
            HashNode<Key, Value> *temp = cur;
            cur = cur->next;
            delete temp;
            temp = NULL;
        }
    }
    delete[] table;
}

template <typename Key, typename Value, typename HashFunc>
bool HashMap<Key, Value, HashFunc>::insert(Key key, Value value)
{                                 //增加一个key-value对
    int index = hash(key) % size; //求出来对于每个key哈希到的地址索引
    HashNode<Key, Value> *hnode = new HashNode<Key, Value>(key, value);
    hnode->next = table[index];
    table[index] = hnode;
    return true;
}

template <typename Key, typename Value, typename HashFunc>
HashNode<Key, Value>* HashMap<Key, Value, HashFunc>::find(const Key &key)
{
    int index = hash(key) % size;
    if (table[index] == nullptr)
        return nullptr;
    HashNode<Key, Value> *cur = table[index];
    while (cur) {
        if (cur->key == key)
            return cur;
        else
            cur = cur->next;
    }
    return nullptr;
}

template <typename Key, typename Value, typename HashFunc>
Value &HashMap<Key, Value, HashFunc>::operator[](const Key &key)
{
    HashNode<Key, Value>* p = find(key);
    if (p == nullptr) {
        insert(key, 0);
        return find(key)->value;
    } else {
        return p->value;
    }
}
